883I - Photo Processing - CodeForces Solution

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

const int N = 300010;

int n, k;
int a[N];
int f[N];

bool check(int x)
{
	memset(f, 0, sizeof f);
	
	f[0] = 1;
	
	int l = 0;
	for (int i = 1; i <= n; i ++ )
	{
		while (a[i - 1] - a[l] > x) l ++ ;
		
		while (i - l >= k)
		{
			if (f[l])
			{
				f[i] = 1;
				break;
			}
			l ++ ;
		}
	}
	
	return f[n];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0); 
	cin >> n >> k;
	for (int i = 0; i < n; i ++ ) cin >> a[i];
	sort(a, a + n);
	int l = 0, r = a[n - 1] - a[0];

	while (l < r)
	{
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}	
	
	cout << l << endl;
	
	return 0;
}